package org.example.algorithm.backtracking;

import java.util.ArrayList;
import java.util.List;

public class NumCombineSolution {

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        if (n < 1 || k == 0) {
            return res;
        }
        List<Integer> list = new ArrayList<>();
        doCombine(res, n, k, 0, list);
        return res;
    }

    private void doCombine(List<List<Integer>> res, int n, int k, int index, List<Integer> list) {
        if (index == k) {
            res.add(new ArrayList<>(list));
        } else {
            int maxNum = list.isEmpty() ? 0 : list.get(list.size()-1);
            for (int i=maxNum+1;i<=n;i++) {
                list.add(i);
                doCombine(res, n, k, index+1, list);
                list.remove(index);
            }
        }
    }

    public static void main(String[] args) {
        NumCombineSolution numCombineSolution = new NumCombineSolution();
        List<List<Integer>> res = numCombineSolution.combine(4, 2);
        System.out.println(res);
    }
}
